package com.sali.DP;

/**
 礼物的最大价值
 */
public class JZ_47 {

    public int maxValue (int[][] grid) {
        int rowLen = grid.length;
        int colLen = grid[0].length;

        // 处理第一行
        for ( int i = 1; i < colLen; i++ ) {
            grid[0][i] += grid[0][i-1];
        }
        // 处理第一列
        for ( int i = 1; i < rowLen; i++ ) {
            grid[i][0] += grid[i-1][0];
        }

        // 处理其他
        for ( int i = 1; i < rowLen; i++ ) {
            for ( int j = 1; j < colLen; j++ ) {
                grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
            }
        }

        return grid[rowLen - 1][colLen - 1];
    }

}
